#define DEBUG
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn=300;

void sort(long long *a, long long *b, int l, int r) {
  int i=l, j=r;
  long long mid=a[(l+r)/2], temp;
  for (; i<=j; ) {
    for (; a[j]>mid; j--);
    for (; a[i]<mid; i++);
    if (i<=j) {
      temp=a[i], a[i]=a[j], a[j]=temp;
      temp=b[i], b[i]=b[j], b[j]=temp;
      i++, j--;
    }
  }
  if (i<r) {
    sort(a, b, i, r);
  }
  if (j>l) {
    sort(a, b, l, j);
  }
}

long long gcd(long long a, long long b) {
  if (a==0 || b==0) {
    return 0;
  }
  for (long long r=a%b; r; a=b, b=r, r=a%b);
  return b;
}

int main() {
  freopen("tree.in", "r", stdin);
  freopen("tree.out", "w", stdout);

  static bool flag[maxn+2][maxn+2];
  static long long k[maxn+2], v[maxn+2];
  int n;
  scanf("%d", &n);
  for (int i=1; i<=n; i++) {
    scanf("%lld %lld", k+i, v+i);
  }

  sort(k, v, 1, n);

  for (int i=0; i<=n+1; i++) {
    for (int j=0; j<=n+1; j++) {
      flag[i][j] = gcd(k[i], k[j])!=1;
    }
  }

  static long long f[maxn+2][maxn+2][2], sum[maxn+2][maxn+2][2];
  static bool book[maxn+2][maxn+2][2];
  for (int i=1; i<=n; i++) {
    if (flag[i][i-1]) {
      f[i][i][0] = sum[i][i][0] = v[i];
      book[i][i][0] = true;
    }
    if (flag[i][i+1]) {
      f[i][i][1] = sum[i][i][1] = v[i];
      book[i][i][1] = true;
    }
    book[i][i-1][0] = book[i][i-1][1] = true;
  }
  book[n+1][n][0] = book[n+1][n][1] = true;
  for (int len=1; len<n; len++) {
    for (int i=1; i+len<=n; i++) {
      int j=i+len;
      for (int t=i; t<=j; t++) {
	if (flag[t][i-1] && book[i][t-1][1] && book[t+1][j][0]) {
	  long long temp=f[i][t-1][1]+f[t+1][j][0]+sum[i][t-1][1]+sum[t+1][j][0]+v[t];
	  if (f[i][j][0]<temp) {
	    f[i][j][0] = temp;
	    sum[i][j][0] = sum[i][t-1][1]+sum[t+1][j][0]+v[t];
	    book[i][j][0] = true;
	  }
	}
	if (flag[t][j+1] && book[i][t-1][1] && book[t+1][j][0]) {
	  if (!flag[t][j+1]) {
	    printf("Error");
	  }
	  long long temp=f[i][t-1][1]+f[t+1][j][0]+sum[i][t-1][1]+sum[t+1][j][0]+v[t];
	  if (f[i][j][1]<temp) {
	    f[i][j][1] = temp;
	    sum[i][j][1] = sum[i][t-1][1]+sum[t+1][j][0]+v[t];
	    book[i][j][1] = true;
	  }
	}
      }
    }
  }

  printf("%lld", book[1][n][0] ? f[1][n][0] : -1);

  fclose(stdin);
  fclose(stdout);
  return 0;
}
